package com.wdc.simple.day05;

import java.awt.*;
import java.util.Arrays;

public class BinarySearchLeftMost {

    public static void main(String[] args) {
        int[] a = {1,2,3,4,4,4,5,9};
        System.out.println(binarySearchRightMost1(a, 4));
//        System.out.println(1>>>1);
//
//        System.out.println(contains(a));

    }

    public static boolean contains(int[] array){
        return Arrays.stream(array).anyMatch(num -> num == 8);
    }

    /**
     *  如果有重复元素则查找最左边的元素， 当然还有最右的
     * @param a
     * @param target
     * @return
     */
    public static int binarySearchLeftMost(int[] a,int target){


        int left = 0;
        int right = a.length - 1;

        int candidate = -1;

        while(left <= right){
            int m = (left+right)>>>1;

            if(a[m] < target){
                left = m +1;
            }else if (a[m] > target) {
                right = m - 1;
            }else {
                candidate = m;
                right =  m - 1;
            }
        }

        return candidate;
    }

    /**  二分查找  LeftMost
     * 返回i 的索引 ，这样可以求排名 、最近邻居、 前任和后任
     * @param a 待查找的升序数组
     * @param target 待查找的目标值
     * @return 返回 >= target 的最靠左的索引
     */

    public static int binarySearchLeftMost1(int[] a,int target){


        int left = 0;
        int right = a.length - 1;

        while(left <= right){

            int m = (left+right)>>>1;

            if(target <= a[m]){
                right = m -1;
            }else  {
                left = m + 1;
            }
        }

        return left;
    }

    /**  二分查找  RightMost
     *  i -1  小于等于目标且最靠右的索引位置
     * @param a   待查找的升序数组
     * @param target 待查找的目标值
     * @return 返回 <= target 的最靠右的索引
     */

    public static int binarySearchRightMost1(int[] a,int target){


        int left = 0;
        int right = a.length - 1;

        while(left <= right){

            int m = (left+right)>>>1;

            if(target < a[m]){
                right = m -1;
            }else  {
                left = m + 1;
            }
        }

        return left -1 ;
    }


}
